package com.learn.algorlthm;

/**
 * @classname:
 * @Description:二进制中1的个数
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-11 13:41
 * 题目描述：
 *  输入一个整数，输出该数二进制表示中1的个数
 */
public class Learn15 {

    //1.Integer.bitCount()
    public static int NumberOf1_1(int n) {
        return Integer.bitCount(n);
    }


    //2. n&(n-l)
    /**
     * O(logM)时间复杂度解法，其中M表示1的个数。
     * 该位运算是去除n的位级表示中最低的那一位。
     *
     * n        :10110100
     * n-1      :10110011
     * n&(n-1)  :10110000
     */
    public static int NumberOf1_2(int n) {
        int cnt = 0;
        while (n != 0) {
            cnt++;
            n&=(n-1);
        }
        return cnt;
    }

}
